class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        #如果 n == 0，不可能生成任何括号组合，直接返回空列表。
        if n == 0:
            return []
        dp = [[""],["()"]]
        #从 2 开始构造到 n 对括号的所有组合，通过以前的结果来构造当前的结果（动态规划的核心思想）。
        for i in range(2,n+1):
            #临时列表 temp 用于收集当前 i 对括号所有合法组合。
            temp = []
            #枚举所有可能的“左右括号划分”方式。对于 i 对括号，将左边括号包裹 j 对，右边再跟上 i - j - 1 对。
            for j in range(i):
                #将 j 对括号放在最内层的一对括号中，剩下的 i - j - 1 对括号放在外部右侧，组合成一个合法括号结构。
                for k in dp[j]:
                    for l in dp[i-j-1]:                        
                        temp.append("("+k+")"+l)
            #把当前构造好的合法组合列表 temp 加入 dp 中，作为 dp[i] 的结果。
            dp.append(temp)
        return dp[-1]
    
